\chapter{有限状态自动机}

\section{字母表}

\subsection{字母表（Alphabet）}

字母表是一个非空的有限集合，一般用$ \Sigma $表示，集合中的元素被称为符号/字符（symbol）。\\

例如：

\begin{itemize}
	\item $ \Sigma = \{0, 1\} $：二进制数集合。
	\item $ \Sigma = \{a, b, \cdots, z\} $：小写字母集合。
	\item $ \Sigma = \{(, ), [, ], \{, \}\} $：括号集合。
\end{itemize}

\vspace{0.5cm}

\subsection{串（String）}

串是一个由字母表中的字符组成的有限序列。\\

例如：

\begin{itemize}
	\item 0011和11是$ \Sigma = \{0, 1\} $上的串。
	\item abc和bbb是$ \Sigma = \{a, b, \cdots, z\} $上的串。
	\item (())和(()是$ \Sigma = \{(, ), [, ], \{, \}\} $上的串。
\end{itemize}

\vspace{0.5cm}

\subsubsection{空串}

空串使用$ \epsilon $表示。\\

\subsubsection{串的长度}

\begin{itemize}
	\item $ |0010| = 4 $
	\item $ |aa| = 2 $
	\item $ |\epsilon| = 0 $
\end{itemize}

\vspace{0.5cm}

\subsubsection{前缀（prefix）}

\begin{itemize}
	\item aa是aaabc的前缀
	\item aaab是aaabc的前缀
	\item aaabc是aaabc的前缀
\end{itemize}

\vspace{0.5cm}

\subsubsection{后缀（suffix）}

\begin{itemize}
	\item bc是aaabc的后缀
	\item abc是aaabc的后缀
	\item aaabc是aaabc的后缀
\end{itemize}

\vspace{0.5cm}

\subsubsection{子串（substring）}

\begin{itemize}
	\item ab是aaabc的子串
	\item aaa是aaabc的子串
	\item aaabc是aaabc的子串
\end{itemize}

\vspace{0.5cm}

\subsubsection{连接（concatenation）}

当$ \omega = abd $，$ \alpha = ce $，那么$ \omega\alpha = abdce $。\\

\subsubsection{指数（exponentiation）}

当$ \omega = abd $，那么$ \omega^3 = abdabdabd $，$ \omega^0 = \epsilon $。\\

\subsubsection{反转（reversal）}

当$ \omega = abd $，那么$ \omega^R = dba $。\\

\subsection{克林闭包（Kleene Closure）}

$ \Sigma^k $用于表示所有在字母表$ \Sigma $上的长度为$ k $的串的集合。\\

例如，$ \Sigma = \{a, b\} $，那么$ \Sigma^2 = \{ab, ba, aa, bb\} $，$ \Sigma^0 = \{\epsilon\} $。\\

克林闭包$ \Sigma^* $用于表示所有在字母表$ \Sigma $上能够组成的串的集合。\\

\vspace{-1cm}

\begin{align}
	\Sigma^* = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \cdots = \bigcup_{k \ge 0}\Sigma^k
\end{align}

正闭包$ \Sigma^+ $则是在$ \Sigma^* $中除了空串以外的所有串的集合。\\

\vspace{-1cm}

\begin{align}
	\Sigma^+ = \Sigma^1 \cup \Sigma^2 \cup \Sigma^3 \cup \cdots = \bigcup_{k > 0}\Sigma^k
\end{align}

\newpage

\section{语言}

\subsection{语言（Language）}

语言是一个字母表中所构成串的集合。\\

例如，$ \Sigma = \{a, b, c, \cdots, z\} $，那么所有英语单词所构成的集合$ L $就是字母表$ \Sigma $上的语言。\\

假设$ A = \{good, bad\} $和$ B = \{boy, girl\} $是两个语言，语言之间可以进行以下操作。\\

\subsubsection{并集（union）}

\vspace{-1cm}

\begin{align}
	A \cup B = \{x\ |\ x \in A \text{ or } x \in B\}
\end{align}

$ A \cup B = \{good, bad, boy, girl\} $\\

\subsubsection{连接（concatenation）}

\vspace{-1cm}

\begin{align}
	A \circ B = \{xy\ |\ x \in A \text{ or } y \in B\}
\end{align}

$ A \circ B = \{goodboy, goodgirl, badboy, badgirl\} $\\

\subsubsection{闭包}

\vspace{-1cm}

\begin{align}
	A^* = \{x_1, x_2, \cdots, x_k\ |\ k \ge 0 \text{ and each } x_i \in A\}
\end{align}

$ A^* = \{\epsilon, good, bad, goodgood, goodbad, badgood, badbad, goodgoodgood, goodgoodbad, \cdots\} $\\

语法和语言与自动机理论密切相关，它们是许多软件实现的基础，例如编译器/解释器、文本编辑器、文本搜索、系统验证等。\\

在自动机理论中，要处理的问题就是判断一个给定的串是否属于某个语言。\\

例如：

\begin{itemize}
	\item $ 0^*10^* $： 只包含一个1的串的集合。

	\item $ \Sigma^*1\Sigma^* $：至少有一个1的串的集合。

	\item $ \Sigma^*001\Sigma^* $：包含子串001的串的集合。

	\item $ (\Sigma\Sigma)^* $：长度为偶数的串的集合。

	\item $ (\Sigma\Sigma\Sigma)^* $：长度为3的倍数的串的集合。
\end{itemize}

\newpage

\section{DFA}

\subsection{DFA（Deterministic Finite Automata）}

有限状态机（FSM, Finite State Machine）用于决定程序当前状态和状态间的切换，状态机最终只能指向一个结果。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[node distance=4cm]
		\node[state, initial, draw, align=center] (s1) {off};
		\node[state, right of=s1, draw, align=center] (s2) {on};

		\draw[->] (s1) edge[above, bend left] node{1} (s2);
		\draw[->] (s2) edge[above, bend left] node{0} (s1);
	\end{tikzpicture}
	\caption{有限状态机}
\end{figure}

确定性有限状态自动机DFA由一个五元组$ (Q, \Sigma, \delta, q_0, F) $表示，其中

\begin{itemize}
	\item $ Q $：状态集合
	\item $ \Sigma $：字母表
	\item $ \delta $：状态转移函数（transition function）
	\item $ q_0 $：初始状态
	\item $ F $：终结状态集合
\end{itemize}

\vspace{0.5cm}

例如DFA可以用来识别空串或者以0结尾的串：

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[state, initial, accepting] (q0) {$ q_0 $};
		\node[state] (q1) at (4,0) {$ q_1 $};

		\draw (q0) edge[loop above] node{0} (q0)
		(q0) edge[bend left, above] node{1} (q1)
		(q1) edge[bend left, below] node{0} (q0)
		(q1) edge[loop above] node{1} (q1);
	\end{tikzpicture}
	\caption{识别空串或以0结尾的串的DFA}
\end{figure}

其中$ Q = \{q_0, q_1\} $，$ \Sigma = \{0, 1\} $，$ q_0 $为初始状态，$ F = \{q_0\} $，$ \delta $为

\begin{table}[H]
	\center
	\begin{tabular}{|c|c|c|}
		\hline
		\multicolumn{1}{|c|}{\multirow{2}{*}{状态}} & \multicolumn{2}{c|}{输入}           \\ \cline{2-3}
		                                            & 0                         & 1       \\
		\hline
		$ q_0 $                                     & $ q_0 $                   & $ q_1 $ \\
		\hline
		$ q_1 $                                     & $ q_0 $                   & $ q_1 $ \\
		\hline
	\end{tabular}
\end{table}

能够被有限自动机接受的语言被称为正则语言（regular language）。\\

例如，构建一个能够识别所有包含子串001的串的DFA：

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[state, initial] (q) {$ q $};
		\node[state] (q0) at (3,0) {$ q_0 $};
		\node[state] (q00) at (6,0) {$ q_{00} $};
		\node[state, accepting] (q001) at (9,0) {$ q_{001} $};

		\draw (q) edge[loop above] node{1} (q)
		(q) edge[bend left, above] node{0} (q0)
		(q0) edge[bend left, below] node{1} (q)
		(q0) edge[above] node{0} (q00)
		(q00) edge[loop above] node{0} (q00)
		(q00) edge[above] node{1} (q001)
		(q001) edge[loop above] node{0,1} (q001);
	\end{tikzpicture}
	\caption{识别包含子串001的串的DFA}
\end{figure}

\vspace{0.5cm}

\subsection{最小化DFA}

有限状态机的最小化，即将一个有限状态机转换为一个更小的有限状态机，使得状态的数目最少。\\

对于两个状态，如果它们之间的转移函数相同，则这两个状态可以合并为一个状态。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[state, initial] (a) {$ a $};
		\node[state] (b) at (0,2) {$ b $};
		\node[state, accepting] (c) at (0,4) {$ c $};
		\node[state] (e) at (3,0) {$ e $};
		\node[state] (f) at (3,2) {$ f $};
		\node[state] (g) at (3,4) {$ g $};
		\node[state] (h) at (3,6) {$ h $};

		\draw (a) edge[left] node{0} (b)
		(a) edge[left] node{1} (f)
		(b) edge[left] node{1} (c)
		(b) edge[left] node{0} (g)
		(c) edge[bend right, left] node{0} (a)
		(c) edge[loop left] node{1} (c)
		(e) edge[bend right, right] node{0} (h)
		(e) edge[left] node{1} (f)
		(f) edge[below] node{0} (c)
		(f) edge[left] node{1} (g)
		(g) edge[loop left] node{0} (g)
		(g) edge[bend left, above] node[yshift=1cm]{1} (e)
		(h) edge[left] node{0} (g)
		(h) edge[left] node{1} (c);
	\end{tikzpicture}
\end{figure}

在这个DFA中，状态$ b $和$ h $是等价的，当接收0时都转移到状态$ g $，当接收1时都转移到状态$ c $。同时状态$ a $和$ e $也是等价的，状态$ a $接收0转移到状态$ b $，状态$ e $接收0转移到状态$ h $，状态$ a $和$ e $接收1时都转移到状态$ f $。\\

因此，状态$ b $和$ h $以及状态$ a $和$ e $可以进行合并。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[state, initial] (ae) {$ [a, e] $};
		\node[state] (bh) at (-2,-2) {$ [b, h] $};
		\node[state] (g) at (2,-2) {$ g $};
		\node[state] (c) at (-4,-4) {$ c $};
		\node[state] (f) at (4,-4) {$ f $};

		\draw (ae) edge[left] node{0} (bh)
		(ae) edge[bend left, right] node{1} (f)
		(bh) edge[above] node{0} (g)
		(bh) edge[left] node{1} (c)
		(c) edge[loop left] node{1} (c)
		(c) edge[bend left, left] node{0} (ae)
		(g) edge[right] node{1} (ae)
		(g) edge[loop below] node{0} (g)
		(f) edge[right] node{1} (g)
		(f) edge[below] node{0} (c);
	\end{tikzpicture}
	\caption{最小化DFA}
\end{figure}

\newpage

\section{NFA}

\subsection{NFA（Non-deterministic Finite Automata）}

在DFA中，每个状态的下一个状态都是唯一确定的，但是非确定性有限状态自动机NFA可能会存在多个下一状态。\\

例如在这个NFA中，状态$ q_0 $存在两个接收1的箭头，而状态$ q_1 $没有接收1的箭头。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[state, initial] (q0) {$ q_0 $};
		\node[state] (q1) at (3,0) {$ q_1 $};
		\node[state] (q2) at (6,0) {$ q_2 $};
		\node[state, accepting] (q3) at (9,0) {$ q_3 $};

		\draw (q0) edge[above] node{1} (q1)
		(q0) edge[loop above] node{0,1} (q0)
		(q1) edge[above] node{0,$ \epsilon $} (q2)
		(q2) edge[above] node{1} (q3)
		(q3) edge[loop above] node{0,1} (q3);
	\end{tikzpicture}
	\caption{NFA}
\end{figure}

因此，在NFA中，每个状态允许对相同输入存在0个、1个或多个转移的状态。如果存在一条能够到达终结状态的路径，那么就称当前的输入是被NFA接受的。\\

\subsection{DFA与NFA的转换}

NFA并不比DFA更加强大，理论证明NFA与DFA是等价的。\\

例如将一个NFA转换为DFA：

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[state, initial] (q0) {$ q_0 $};
		\node[state, accepting] (q1) at (5,0) {$ q_1 $};

		\draw (q0) edge[loop above] node{0} (q0)
		(q0) edge[bend left, above] node{0} (q1)
		(q0) edge[above] node{1} (q1)
		(q1) edge[bend left, below] node{1} (q0)
		(q1) edge[loop above] node{1} (q1);
	\end{tikzpicture}
\end{figure}

构建一个与NFA等价的DFA，只需将NFA中转换到的状态集合作为DFA中的一个状态即可。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[state, initial] (q0) {$ \{q_0\} $};
		\node[state, accepting] (q1) at (5,0) {$ \{q_1\} $};
		\node[state, accepting] (q0q1) at (0,-4) {$ \{q_0, q_1\} $};
		\node[state] (e) at (5,-4) {$ \{\epsilon\} $};

		\draw (q0) edge[left] node{0} (q0q1)
		(q0) edge[above] node{1} (q1)
		(q1) edge[loop above] node{1} (q1)
		(q1) edge[left] node{1} (q0q1)
		(q1) edge[right] node{0} (e)
		(q0q1) edge[loop left] node{0,1} (q0q1)
		(e) edge[loop right] node{0,1} (e);
	\end{tikzpicture}
	\caption{NFA转换DFA}
\end{figure}

\vspace{0.5cm}

\subsection{$ \epsilon $-NFA}

$ \epsilon $-NFA允许不消耗输入字符在状态之间转移。\\

例如以下$ \epsilon $-NFA能够接受小数，如+3.14、-0.12、.71、2.等。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\node[state, initial] (q0) {$ q_0 $};
		\node[state] (q1) at (2.5,0) {$ q_1 $};
		\node[state] (q2) at (5,0) {$ q_2 $};
		\node[state] (q3) at (7.5,0) {$ q_3 $};
		\node[state] (q4) at (5,-3) {$ q_4 $};
		\node[state, accepting] (q5) at (10,0) {$ q_5 $};

		\draw (q0) edge[above] node{$ \epsilon, +, - $} (q1)
		(q1) edge[loop above] node{[0-9]} (q1)
		(q1) edge[above] node{.} (q2)
		(q1) edge[left] node{[0-9]} (q4)
		(q2) edge[above] node{[0-9]} (q3)
		(q3) edge[loop above] node{[0-9]} (q3)
		(q4) edge[right] node{.} (q3)
		(q3) edge[above] node{$ \epsilon $} (q5);
	\end{tikzpicture}
	\caption{接受小数的$ \epsilon $-NFA}
\end{figure}

\newpage

\section{正则表达式}

\subsection{编译器（Compiler）}

编译器是一种特殊的程序，可以将一种编程语言的源代码翻译成机器码、字节码或另一种编程语言。\\

编译器包含以下阶段：

\begin{enumerate}
	\item 词法分析器（lexical analyzer）
	\item 语法分析器（syntex analyzer）
	\item 语义分析器（semantic analyzer）
	\item 中间代码生成器（intermediate code generator）
	\item 代码优化器（code optimizer）
	\item 代码生成器（code generator）
\end{enumerate}

\vspace{0.5cm}

\subsection{词法分析}

词法分析是编译器的第一步，它的主要任务是读取源代码，并生成能够被解析器（parser）进行语法分析的tokens和语法书（syntex tree）。\\

例如time = hour * 60 + minute，经过词法分析后，将会得到：

\begin{itemize}
	\item id(time)
	\item assignment(=)
	\item id(hour)
	\item op(*)
	\item num(60)
	\item op(+)
	\item id(minute)
\end{itemize}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[
			-,
			level distance=2cm,
			level 1/.style={sibling distance=5cm},
			level 2/.style={sibling distance=3cm},
			level 3/.style={sibling distance=3cm}
		]
		\node {assignment(=)}
		child {
				node {id(time)}
			}
		child {
				node {op(+)}
				child {
						node {op(*)}
						child {
								node {id(hour)}
							}
						child {
								node {num(60)}
							}
					}
				child {
						node {minute}
					}
			};
	\end{tikzpicture}
	\caption{语法树}
\end{figure}

\vspace{0.5cm}

\subsection{正则表达式（Regex, Regular Expression）}

正则表达式描述了字符串匹配的模式（pattern），可以用来检查一个串是否包含某个子串、替换子串、或提取符合条件的子串。像grep、vi、python、lex等工具都支持正则表达式的使用。\\

例如用于匹配一个合法的变量名的正则表达式为[a-zA-Z\_][a-zA-Z0-9\_]*。即变量名只能由字母或下划线开头，后面可以是任意多个字母、数字或下划线。\\

正则表达式支持以下操作：

\begin{itemize}
	\item 连接：$ ab $或$ a \cdot b $
	\item 选择：$ a\ |\ b $
	\item 克林闭包：$ a^* = \{\epsilon, a, aa, aaa, \cdots\} $
	\item 匹配至少1次：$ a^+ = aa^* $
	\item 匹配0次或1次：$ a? = a\ |\ \epsilon $
	\item 匹配任意字符：$ . $
	\item 补集：$ ~(a\ |\ b) $
\end{itemize}

\vspace{0.5cm}

其中克林闭包运算的优先级最高，其次是连接，最后是选择。\\

例如$ (a\ |\ b)^*aa(a\ |\ b)^* $用于匹配包含连续的a的串，$ b^*(abb^*)^*(a\ |\ \epsilon) $用于匹配没有连续的a的串。\\

然而$ \{a^nb^n\ |\ n \ge 0\} $却不是正则语言，因为它无法用有限个状态来验证a和b的出现次数是相等的。\\

\newpage